package com.hy.java.utility.math.numbertheory;

import java.util.ArrayList;
import java.util.List;

public class PrimeNumber {
	/**
	 * 判断n是不是质数
	 */
	public static boolean isPrimeNumber(int n) {
		// 从是否小于2开始判断
		if (n < 2) {
			return false;
		}
		// 判断到2或3
		if (n == 2 || n == 3) {
			return true;
		}
		// 从4开始，判断是否为偶数，若是偶数则直接结束
		if (n % 2 == 0) {
			return false;
		}
		// 若为大于4的奇数，则用质数定义去判断（只需判断奇数因子即可）
		double sqrt = Math.sqrt(n);
		for (int i = 3; i <= sqrt; i += 2) {
			if (n % i == 0) {
				return false;
			}
		}
		// 若能走到这儿，说明是质数
		return true;
	}

	/**
	 * 返回第n个质数
	 */
	public static int nthPrimeNumber(int n) {
		// 第0个质数是异常
		int alreadyFound_primeNumber_count = 0;
		int prime = -1;
		// 第1个质数是2
		if (n > 0) {
			prime = 2;
			alreadyFound_primeNumber_count++;
			// 第2个质数是3（变成奇数了，所以后面再找的话只看奇数即可）
			if (n > 1) {
				prime = 3;
				alreadyFound_primeNumber_count++;
				// 如果还得往后找质数，则只找奇数即可
				while (alreadyFound_primeNumber_count < n) {
					// 找下一个质数
					do {
						prime += 2;
					} while (!PrimeNumber.isPrimeNumber(prime));
					// 找到下一个质数后，对比count是否到达n
					alreadyFound_primeNumber_count++;
				}
			}
		}
		return prime;
	}

	/**
	 * 返回小于n的所有质数
	 */
	public static List<Integer> primeNumbersBeforeN(int n) {
		List<Integer> res = new ArrayList<>();
		if (n > 2) {
			res.add(2);
			for (int x = 3; x < n; x += 2) {
				if (PrimeNumber.isPrimeNumber(x)) {
					res.add(x);
				}
			}
		}
		return res;
	}
}
